import { Dict, IRect } from "../util/Defined";

/** 缓存象限数组 key值为象限bit */
const idxsDic: Dict<readonly number[]> = { 0: [] };
for (let i = 0; i < 4; ++i) {
    let bit = 1 << i;
    idxsDic[bit] = [i];
    for (let j = i + 1; j < 4; ++j) {
        let bit2 = bit | 1 << j;
        idxsDic[bit2] = [i, j];
        for (let k = j + 1; k < 4; ++k) {
            let bit3 = bit2 | 1 << k;
            idxsDic[bit3] = [i, j, k];
            for (let l = k + 1; l < 4; ++l) {
                idxsDic[bit3 | 1 << l] = [i, j, k, l];
            }
        }
    }
}


/**
 * 四叉树
 */
export class QuadTree<T = any> {

    /** 根节点树 */
    root: QuadTree<T>;
    /** 当前四叉树包含物体 */
    items = new Map<T, IRect>();
    /** 分裂的子树 */
    children: QuadTree<T>[];
    /** 当前深度 */
    readonly level: number;

    protected _halfX: number;
    protected _halfY: number;
    protected _halfWidth: number;
    protected _halfHeight: number;
    protected _coverItems = new Set<T>();
    protected _emptyNodes: QuadTree[] = [];

    constructor(
        /** 边界范围 xy零点为左下 */
        public rect: Readonly<IRect>,
        /** 最大容纳物体数量 超过时将分裂成新的四叉树 */
        public maxObj: number,
        /** 最大深度 达到后将不再分裂 */
        public maxLevel = 4,
        /** 父树 */
        public parent?: QuadTree<T>
    ) {
        this._halfWidth = this.rect.width / 2;
        this._halfHeight = this.rect.height / 2;
        this._halfX = this.rect.x + this._halfWidth;
        this._halfY = this.rect.y + this._halfHeight;
        this.level = parent ? parent.level + 1 : 0;
        if (parent) {
            this.root = parent.root;
        } else {
            this.root = this;
        }
    }

    /**
     * 获取矩形范围覆盖哪些象限
     * @param rect 矩形范围 xy零点为左下
     */
    getCoverIdx(rect: Readonly<IRect>): readonly number[] {

        const left = rect.x <= this._halfX,
            up = rect.y + rect.height >= this._halfY,
            right = rect.x + rect.width >= this._halfX,
            down = rect.y <= this._halfY;

        let bit = 0;
        //第一象限 右上
        if (right && up) {
            bit |= 1;
        }

        //第二象限 左上
        if (left && up) {
            bit |= 1 << 1;
        }

        //第三象限 左下
        if (left && down) {
            bit |= 1 << 2;
        }

        //第四象限 右下
        if (right && down) {
            bit |= 1 << 3;
        }

        return idxsDic[bit];
    }

    protected split() {

        //第一象限 右上
        this.children = [];
        this.children[0] = new QuadTree({
            x: this._halfX,
            y: this._halfY,
            width: this._halfWidth,
            height: this._halfHeight
        }, this.maxObj, this.maxLevel, this);

        //第二象限 左上
        this.children[1] = new QuadTree({
            x: this.rect.x,
            y: this._halfY,
            width: this._halfWidth,
            height: this._halfHeight
        }, this.maxObj, this.maxLevel, this);

        //第三象限 左下
        this.children[2] = new QuadTree({
            x: this.rect.x,
            y: this.rect.y,
            width: this._halfWidth,
            height: this._halfHeight
        }, this.maxObj, this.maxLevel, this);

        //第四象限 右下
        this.children[3] = new QuadTree({
            x: this._halfX,
            y: this.rect.y,
            width: this._halfWidth,
            height: this._halfHeight
        }, this.maxObj, this.maxLevel, this);
    }

    /**
     * 插入一个物体
     * @param item 物体
     * @param rect 物体的矩形范围 xy零点为左下
     */
    addItem(item: T, rect: Readonly<IRect>) {

        //如果有子树节点 则由子树判断是否插入
        if (this.children) {
            const idxs = this.getCoverIdx(rect);
            for (let i = 0; i < idxs.length; ++i) {
                this.children[idxs[i]].addItem(item, rect);
            }
            return;
        }

        this.items.set(item, rect);

        //判断是否分裂
        if (this.items.size > this.maxObj && this.level < this.maxLevel) {

            this.split();

            //将所有物体分配到分裂的子树上
            this.items.forEach((rect, item) => {
                const idxs = this.getCoverIdx(rect);
                for (let i = 0; i < idxs.length; ++i) {
                    this.children[idxs[i]].addItem(item, rect);
                }
            });

            this.items.clear();
        }
    }

    /**
     * 移除物体
     * @param item 
     */
    removeItem(item: T) {
        this.items.delete(item);
        this.children?.forEach(child => {
            child.removeItem(item);
        });
    }

    /**
     * 获取矩形范围覆盖的所有物体
     * @param rect 矩形范围 xy零点为左下
     * @returns 返回的set是个只读临时变量，会在下次返回时被修改，不要保持引用
     */
    getCoverItems(rect: Readonly<IRect>) {
        this._coverItems.clear();
        if (this.children) {
            const idxs = this.getCoverIdx(rect);
            for (let i = 0; i < idxs.length; i++) {
                this.children[idxs[i]].getCoverItems(rect).forEach(item => {
                    this._coverItems.add(item);
                });
            }
        } else {
            this.items.forEach((_, item) => {
                this._coverItems.add(item);
            });
        }
        return this._coverItems;
    };

    /**
     * 获取所有没有物体的节点
     * @returns 返回的数组t是个只读临时变量，会在下次返回时被修改，不要保持引用
     */
    getEmptyNodes(): readonly QuadTree[] {
        this._emptyNodes.length = 0;
        if (this.children) {
            this.children.forEach(child => {
                this._emptyNodes.push(...child.getEmptyNodes());
            });
        } else if (this.items.size === 0) {
            this._emptyNodes.push(this);
        }
        return this._emptyNodes;
    }

    /**
     * 清理四叉树
     */
    clear() {
        this.parent = null;
        if (this.children) {
            for (let i = 0; i < this.children.length; ++i) {
                this.children[i].clear();
                this.children[i].root = null;
            }
            this.children = null;
        }
        this.items.clear();
        this._coverItems.clear();
        this._emptyNodes.length = 0;
    };

}